package com.unit;

import java.util.ArrayList;
import java.util.List;

public class ArrayAndString {
    /**
     * 给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
     * @param nums
     * @return
     */
    public int[] productExceptSelf(int[] nums) {
        int len=nums.length;
        int []result=new int[len];
        result[len-1]=1;
        for (int i=len-2;i>=0;i--){
            result[i]=result[i+1]*nums[i+1];
        }
        int left=1;
        for(int i=0;i<len;i++){
            result[i]=left*result[i];
            left=left*nums[i];
        }
        return result;
    }

    /**
     * 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list=new ArrayList<>();
        int H=matrix.length;
        if(H<=0) return list;
        int W=matrix[0].length;
        spirallevelOrder(matrix,list,0,0,H,W);
        return list;
    }
    private void spirallevelOrder(int[][] matrix, List<Integer> list, int i, int j, int h, int w) {
        if(h-i==1&&w-j==1){
            list.add(matrix[i][j]);
            return;
        }else if(h-i==1){
            for(int b=j;b<w;b++){
                list.add(matrix[i][b]);
            }
            return;
        }else if(w-j==1){
            for(int a=i;a<h;a++){
                list.add(matrix[a][j]);
            }
            return;
        }else if(h<=i||w<=j){
            return;
        }
        for(int b=j;b<w-1;b++){
            list.add(matrix[i][b]);
        }
        for(int a=i;a<h-1;a++){
            list.add(matrix[a][w-1]);
        }
        for(int b=w-1;b>j;b--){
            list.add(matrix[h-1][b]);
        }
        for(int a=h-1;a>i;a--){
            list.add(matrix[a][j]);
        }
        spirallevelOrder(matrix,list,i+1,j+1,h-1,w-1);
    }

    /**
     * 第一个缺失的正数
     * 给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
     * @param nums
     * @return
     */
    public int firstMissingPositive(int[] nums) {
        int len=nums.length;
        boolean []visit=new boolean[len+1];
        visit[0]=true;
        for(int i=0;i<len;i++){
            int num=nums[i];
            if(num<0)continue;
            else if(num>len)continue;
            else {
                visit[num]=true;
            }
        }
        for(int i=0;i<=len;i++){
            if(visit[i])continue;
            else return i;
        }
        return len+1;
    }
}
